The present invention relates to addressing circuits used to control the access to memory locations within a memory device, more particularly to addressing circuits used to generate addresses for accessing circular buffers.
In many electronic circuits, there is a need to access, or address, certain periodically consecutive memory locations in a cyclic manner. This allows an unlimited number of read or write operations to be carried out in sequence, using only a small portion of the available memory. One memory location is addressed, then the next and so on until the end of a predefined memory area--the buffer--is reached. Addressing then returns to a location at the other end of the buffer. Typically, addressing begins at the lowest address available and increases until an upper limit is reached, and memory access is returned to the lowest available address in a wraparound step. Of course, the addressing could equally begin at the highest address available and decrease until a lower limit is reached, and memory access is returned to the highest available address in a wraparound step. This is known as circular, or modulo addressing, and the buffer is known as a circular or modulo addressed buffer.
The calculation of the addresses for use when accessing memory locations within such a circular buffer may be done in software installed on an associated microprocessor. These software techniques, however, require several operating cycles to complete a calculation and are too slow for certain applications, such as digital filtering, matrix manipulation and many other digital signal processing routines. Hardware addressing methods are therefore often preferred for their speed of operation. Such modulo addressing may be carried out in hardware by a circuit such as described in an international patent application number PCT/US91/08102, publication number WO 92/08186 from Analog Devices Inc.
FIG. 1 illustrates the typical organization of a simple circular buffer of the prior art. A series of memory locations are dedicated to the buffer. These locations have a lowest location 3 and a highest location 4. Other memory locations, for example 6, 8 are present at intermediary address locations. The address of memory location 14 just beyond the upper limit of the buffer, is used in the wraparound procedure. A control circuit controls the access to the memory locations of the buffer by generating and supplying an absolute current address of each memory location to a pointer register. The action of this control circuit is represented by a moving pointer 16.
Supposing the memory location 6 is being read, with pointer 16 pointing to this location. Once this is done, the address pointer 16 is incremented by one and memory location 8 is pointed at for reading or writing during the following cycle. This continues in an identical manner until the final memory location 4 in the buffer is read. The address supplied to the pointer 16 is incremented by one and becomes the address of memory location 14, in excess of the buffer's upper address limit. The control circuitry detects the presence of the address of location 14 in the register holding the pointer's input address, the control circuit resets the contents of this register and the memory location 3 with the lowest address is pointed to and accessed next. In this buffer, each location is accessed, one after the other, in sequence. Reaching the end of the buffer is detected by the control circuitry when address of the memory location 14 just beyond the upper limit of the buffer is supplied to the pointer.
The control circuitry of such a buffer may be arranged such that a register is loaded with (M-1), where M is the number of locations in the buffer, and the contents of this register are decremented at each read or write cycle, and when the contents of the register reach 0, the register is reset to contain (M-1). The contents of the register are added to the address of the lowest location within the buffer. There are no limitations on the size of the buffer, nor the start address of the buffer. They may be of any size. This buffer will not work if the address is incremented in steps of two or more memory locations, as the memory location 14 may be skipped.
FIG. 2 illustrates another circular buffer of the prior art. A plurality of memory locations are included within the buffer. The buffer has a lowest addressed location 23 and a highest addressed location 24. Memory locations 25, 27, 31, 32 lie between these two limits. A control circuit controls the access to the memory locations of the buffer by generating and supplying the absolute address of each memory location. This is represented by a moving pointer 33.
This buffer allows memory accesses with steps greater than one location to be used. The buffer must contain a number of memory locations which is an integral power of 2. If the buffer contains 2 n locations, the lowest address 23 of the buffer must have all of its n least significant bits equal to 0. The highest address of the buffer will then have all of its n lowest bits equal to 1. Taking as an example the case where n=8, the buffer will have 28=256 locations. The pointer is currently pointing to location 27, which may have the 12 bit address 110010101000. Let us suppose that the buffer control circuitry is incrementing the addresses in steps of four. The next location pointed to will be location 31, with address 110010101100. This will continue until the end of the buffer is almost reached. After addressing location 32, with--for example--an address 110011111110, the address is incremented by four to 110100000010. This lies outside the buffer, and is detected by the control circuitry by the change in bit 8. Bit 8 is then reset to 0 and the new address is 110000000010, location 25, near the lowest address end of the buffer. The control circuitry for this buffer is much more complex than that required for the buffer of FIG. 1. The simplest circuitry is obtained when the buffer is used according to all of the above-mentioned restrictions; that is that the buffer must be of length 2 n, and must start at a location whose address is an integer multiple of 2 n, in order to have its n least significant bits equal to 0.
By using extra circuitry, it is possible to provide a circular buffer of lengths other than powers of two. For example, a 120 location circular buffer may be provided by detecting a change in the 8th bit of the output of an adder connected to add 8 to the pointer address.
There is also a requirement to be able to decrement the accessed address by any number of locations, and to have the buffer any length, not necessarily a multiple of 2 n.
The required operation of a circular buffer is to detect the passing of the upper address limit, and return the pointer to the correct number of locations above the lower address limit, being equal to the length of the overshoot beyond the upper limit address, in the case of positive increments.
Using the symbols Addr for the current address, Nadr for the next address, Inc for the increment, Ladd for the lower address limit and Hadd for the upper address limit, the next address Nadr will be: EQU Addr+Inc,
unless this is greater than Hadd, in which case, the next address needs to be: EQU Nadr=Addr+Inc-Hadd+Ladd-1.
For example, for a buffer with upper address limit 120, lower address limit 10, a current address of 117 and an increment of +4, EQU Nadr=117+4-120+10-1=10.
Conversely, when a negative increment is used, the required operation of a circular buffer is to detect the passing of the lower address limit, and return the pointer to the correct number of locations below the upper address limit, being equal to the length of the overshoot below the lower address limit, in the case of negative increments.
Using the same symbols and the same example, but with a decrement of 4, the next address will be: EQU Addr+Inc,
as Inc is a signed integer, unless this is less than the lower address limit, in which case the next address will be: EQU Nadr=Addr+Inc+Hadd-Ladd+1.
Supposing the current address is 12, the next address will be: EQU Nadr=12-4+120-10+1=119.
The above referenced patent application attempts to solve a problem resulting from the limitations imposed by the above described buffers by providing four registers of N bits, which hold: a first boundary address in the buffer; the next address to be accessed; the increment value and the length of the buffer. Either the first boundary address register or the length register may be replaced by a register which contains a second boundary address of the register. Incrementation and address wraparound is performed in such a way that the buffer may be of any length and located at any position in memory. The contents of the increment register are added to the contents of the current address register, and if this sum exceeds the limit of the buffer, an alternative address is selected, being the alternative described above. However, this circuit suffers from certain problems.
Firstly, the circuit is rather complicated, involving the use of at least four different circuit blocks, namely a multiplexer, an adder, an adder/subtractor and a comparator. This makes it difficult to optimize the circuit to obtain optimum performance from any given manufacturing process, as each block must be individually optimized, and then the effects of one block on the others connected to it must be considered. Thus the circuit is likely to operate at a non-optimum speed, and any change in manufacturing process would require a considerable optimization effort. Secondly, the circuit makes the decision as to which of the two possible next addresses are to be used right at the end of the processing. Two addresses are calculated, then the first provisional next address is compared to a fixed limit address or buffer length to determine which provisional next address is to be used. The use of a multiple bit comparator introduces delays due to the complexity of such a circuit block, and its inclusion into the critical path of calculation of the next address means that an additional delay is introduced after both provisional next addresses have been calculated.
The object of the current invention is to provide a simple, fast hardware circular buffer addressing circuit which allows modulo addressing of a buffer of any size, located at any address in the memory, and within which the pointer may be incremented or decremented at each addressing operation by any amount up to the size of the buffer. Furthermore, the invention seeks to provide such a circuit with a reduced critical path to ensure fastest possible operation, simple circuitry to facilitate optimization of operation and ease of adaptation to manufacturing processes. The invention also seeks to provide a circuit which is easily scaleable for any size of buffer, and any length of addressing used.
More particularly, in accordance with the invention, a circuit is described for incrementing a current access address of a circular buffer in an electronic memory by an increment to produce a next address. This circuit includes an adder circuit for adding the current address to the increment and producing a first provisional next address and a circuit which causes the next address to return to a base address plus an overshoot, when the incremented address passes a limit address by a number equal to the overshoot. For the calculation of the next address, there is provided an adder circuit including only three adders receiving the current address, the increment and the limit address and producing a first and a second provisional next address and the difference between the first provisional next address and the limit address; and a selection circuit for selecting as the next address one of the two provisional next addresses, the selection being made upon the polarity of the difference between the first provisional next address and the limit address.
The increment may be of either positive or negative polarity, which may be selected while the circuit is in operation. Equally, the magnitude of the increment and the limit addresses of the buffer may be selected while the circuit is in operation.
Such a circuit may have a first adder which adds the current address and the increment to produce a first provisional next address and a second adder which adds or subtracts, depending on the polarity of the increment, the first provisional next address and the limit address to produce the difference value and a signal indicating the passing of the limit address by the first provisional address; and a third adder which adds or subtracts, depending on the polarity of the increment, the difference value and the base address to produce a second provisional next address.
The second and third adders may receive a signal on a carry input indicating the polarity of the increment.
In alternative preferred embodiments, either: one of the inputs of each of the second and third adders is connected to the output of a first and a second inverter, respectively; or one of the inputs of the second adder is connected to the output of a third inverter.
In particular, the circuit may comprise: a first two-input adder whose output is connected to an input of a first two-input multiplexer and further connected to a first input of a second two-input adder; the output of the second two-input adder being connected to a first input of a third two-input adder; the output of the third two-input adder being connected to a second input of the first multiplexer; the output of the first multiplexer being connected to a first input of the first two-input adder; further comprising a connection between a carry out output of the second two-input adder and a control terminal of the first multiplexer.
The circuit may further include second and third multiplexers whose outputs are connected to second inputs of the second and third adders respectively and whose first, second and control inputs are respectively connected together.
In the alternative preferred embodiments, either a first inverter is included between the output of the first adder and the first input of the second adder and a second inverter is included between the output of the second adder and the first input of the third adder; or a third inverter is connected between the output of the second multiplexer and the second input of the second adder.
The circuit will preferably further include a connection between the control input of the second multiplexer and a carry in input of the third adder in the first embodiment; and a connection between the control input of the second multiplexer and carry in inputs of the second and the third adders in the second embodiment.
The objects of the current invention may be achieved as described below in reference to specific embodiments, with reference to FIGS. 3 and 4 of the accompanying drawings wherein: